% The GA function
% Returns the hypothesis from P that has the highest fitness

function [fittestHypothesis] = hw8GA(inputData, numHypo, crossoverFrac, mutationRate,numGens)
[inputSize, numElements] = size(inputData);
% Calculating number of bits for  representation of hypothesis
numSwaps = (numElements*(numElements -1))/2;
numBits = 1;
while (2^numBits < numElements)
    numBits = numBits + 1;     
end

%generating the hypothesis
population = int16((numElements-1)*rand(numHypo,2*numSwaps)+1);
numHypoToInclude = (1 - crossoverFrac)*numHypo;
%caculating fit for each input and the max fitness
[popFitness, relativeFit] = hw8Fitness(inputData, population);

newGenerationSize = 2*numSwaps*numBits;
% The GA algorithm till the max fitness is less than the threshold we need
k = 1;
while(k < numGens)
    % Select
    selectedGeneration = hw8Select(population, numHypoToInclude, relativeFit);
%    disp('selected');
    % creating new generation from decimal to binary
    newGeneration = hw8PopDecToBin(selectedGeneration,newGenerationSize,numBits);
%    disp('dectobin');
    %Crossover
    numPairs = (numHypo*crossoverFrac)/2;
    crossGeneration = hw8Crossover(newGeneration,numPairs);
%    disp('dcrossed');
    %Mutate
    finalGeneration = hw8Mutate(crossGeneration,mutationRate);
%    disp('mutated');
    population = hw8PopBinToDec(finalGeneration, 2*numSwaps,numBits);
%    disp('bintodec');
    [popFitness, relativeFit] = hw8Fitness(inputData, population);
end
[sortedtFitness, fitIdx] = sort(popFitness, 'descend');
fittestHypothesis = population(fitIdx(1),:);

